package com.zhugang.week03;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program algorithms
 * @description: removeDuplicates
 * @author: chanzhugang
 * @create: 2022/06/05 16:29
 */
public class RemoveDuplicates {

    /**
     * 1047. 删除字符串中所有相邻重复项
     * abbaca   -> ca
     *
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        // 用LinkedList实现
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (deque.isEmpty() || deque.peekLast() != c) {
                deque.addLast(c);
            } else {
                deque.pollLast();
            }
        }
        StringBuilder builder = new StringBuilder();
        while (!deque.isEmpty()) {
            builder.append(deque.pollFirst());
        }
        return builder.toString();
    }
}